﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;

namespace ESpace
{
    /// <summary>Класс фии, возаращающей является ли ячейка препятствием</summary>
    public delegate bool IsObstracleDelegate(int X, int Y);
    /// <summary>Класс фии, возаращающей является ли ячейка освещенной</summary>
    public delegate bool IsLightingDelegate(int X, int Y);

    /// <summary>Направления ходов в лабиринте в 4-х направлениях</summary>
    public enum TrackAction { moveUp, moveDown, moveLeft, moveRight };
    /// <summary>Направления ходов в лабиринте в 8-ми направлениях</summary>
    public enum TrackAction8 { moveUp, moveDown, moveLeft, moveRight, moveUpLeft, moveUpRight, moveDownLeft, moveDownRight };

    /// <summary>Лабиринт</summary>
    public class Labyrinth
    {
        #region *** Освещенная область ***************************************

        /// <summary>
        /// Область распространения света на расстояние Radius с центром в точке X:Y. (Radius=1 означает распространение света на 1 клетку во все стороны)
        /// Возвращает лист освещеных клеток. При этом если свет упирается в препятствие, оно освещается. 
        /// </summary>
        /// <param name="X">Положение центра по X</param>
        /// <param name="Y">Положение центра по Y</param>
        /// <param name="Radius">радиус распространения света</param>
        /// <param name="Direction">направление распространения света (от 0 до 359. 0 - направление точно слава направо)</param>
        /// <param name="Angle">угол распространения света (от 1 до 360)</param>
        /// <param name="IsObstracle">Функция, определяющая препятствие по координатам</param>
        /// <param name="mtrWidth">Ширина поля</param>
        /// <param name="mtrHeight">Высота поля</param>
        public static List<Point> LightRange(int X, int Y, int Radius, int Direction, int Angle, IsObstracleDelegate IsObstracle, int mtrWidth, int mtrHeight)
        {
            List<Point> ret = new List<Point>();
            ret.Add(new Point(X, Y));

            int startX = X - Radius; if (startX < 0) startX = 0; // Left точка прямоугольника участка матрицы
            int startY = Y - Radius; if (startY < 0) startY = 0; // Top точка прямоугольника участка матрицы
            int endX = X + Radius; if (endX >= mtrWidth) endX = mtrWidth - 1; // Right точка прямоугольника участка матрицы
            int endY = Y + Radius; if (endY >= mtrHeight) endY = mtrHeight - 1; // Bottom точка прямоугольника участка матрицы

            // матрица клеток, которые не нужно проверять (уже проверенных или не в радиусе). Нужна для ускорения алгоритма так как проверяемые точки часто пересекаются
            int w = Radius * 2 + 1; int h = Radius * 2 + 1;
            bool[,] mtr = new bool[w, h];

            // отмечаем клетки не в радиусе или не в луче света
            int nX = Radius; if ((X - Radius) < 0) nX += (X - Radius);
            int nY = Radius; if ((Y - Radius) < 0) nY += (Y - Radius);
            for (int i = 0; i < w; i++)
                for (int j = 0; j < h; j++)
                {
                    mtr[i, j] = !CellInRadius(nX, nY, i, j, Radius) || !CellInRay(nX, nY, i, j, Radius, Direction, Angle);
                   
                }

            // пробегаемся по всем крайним точкам
            // строим до них линии от центра
            // и смотрим, какие клетки видимы

            #region *** построение линий и добавление освещенных точек ***
            for (int i = startX; i <= endX; i++)
            {
                // строим линию до точки i:startY
                List<Point> pl = GetListPointInLine(X, Y, i, startY);
                for (int p = 0; p < pl.Count; p++)
                    if (IsObstracle(pl[p].X, pl[p].Y))
                    {
                        if (!mtr[pl[p].X - startX, pl[p].Y - startY]) { ret.Add(pl[p]); mtr[pl[p].X - startX, pl[p].Y - startY] = true; }
                        break;
                    }
                    else if (!mtr[pl[p].X - startX, pl[p].Y - startY]) { ret.Add(pl[p]); mtr[pl[p].X - startX, pl[p].Y - startY] = true; }

                // строим линию до точки i:endY
                pl = GetListPointInLine(X, Y, i, endY);
                for (int p = 0; p < pl.Count; p++)
                    if (IsObstracle(pl[p].X, pl[p].Y))
                    {
                        if (!mtr[pl[p].X - startX, pl[p].Y - startY]) { ret.Add(pl[p]); mtr[pl[p].X - startX, pl[p].Y - startY] = true; }
                        break;
                    }
                    else if (!mtr[pl[p].X - startX, pl[p].Y - startY]) { ret.Add(pl[p]); mtr[pl[p].X - startX, pl[p].Y - startY] = true; }
            }

            for (int j = startY; j <= endY; j++)
            {
                // строим линию до точки startX:j
                List<Point> pl = GetListPointInLine(X, Y, startX, j);
                for (int p = 0; p < pl.Count; p++)
                    if (IsObstracle(pl[p].X, pl[p].Y))
                    {
                        if (!mtr[pl[p].X - startX, pl[p].Y - startY]) { ret.Add(pl[p]); mtr[pl[p].X - startX, pl[p].Y - startY] = true; }
                        break;
                    }
                    else if (!mtr[pl[p].X - startX, pl[p].Y - startY]) { ret.Add(pl[p]); mtr[pl[p].X - startX, pl[p].Y - startY] = true; }

                // строим линию до точки endX:j
                pl = GetListPointInLine(X, Y, endX, j);
                for (int p = 0; p < pl.Count; p++)
                    if (IsObstracle(pl[p].X, pl[p].Y))
                    {
                        if (!mtr[pl[p].X - startX, pl[p].Y - startY]) { ret.Add(pl[p]); mtr[pl[p].X - startX, pl[p].Y - startY] = true; }
                        break;
                    }
                    else if (!mtr[pl[p].X - startX, pl[p].Y - startY]) { ret.Add(pl[p]); mtr[pl[p].X - startX, pl[p].Y - startY] = true; }
            }
            #endregion *** построение линий и добавление освещенных точек ***

            return ret;
        }

        // нахождение методом выстрела (стреляем на всю длину матрицы) 
        public static List<Point> LightRange(int X, int Y, int Radius, int Direction, int Angle, IsObstracleDelegate IsObstracle, IsLightingDelegate IsLighting, int mtrWidth, int mtrHeight)
        {
            List<Point> ret = new List<Point>();
            ret.Add(new Point(X, Y));

            // матрица клеток, которые не нужно проверять (уже проверенных)
            bool[,] mtr = new bool[mtrWidth, mtrHeight];

            // пробегаемся по всем крайним точкам
            // строим до них линии от плеера
            // и смотрим, какие клетки видимы
            // как бы стреляем от плеера в сторону крайней клетки до тех пор, пока не дойдем до этой клетки или не упремся в препятствие

            #region *** построение линий и добавление освещенных точек ***
            // пробегаемся по всем крайним точкам по X
            for (int i = 0; i < mtrWidth; i++)
            {
                // стреляем в верхние точки
                List<Point> pl = GetListPointInLine(X, Y, i, 0);
                for (int p = 0; p < pl.Count; p++) 
                    if (!CheckPoint(ret, X, Y, pl[p], mtr, Radius, Direction, Angle, IsObstracle, IsLighting)) break;

                // стреляем в нижние точки
                pl = GetListPointInLine(X, Y, i, mtrHeight - 1);
                for (int p = 0; p < pl.Count; p++) 
                    if (!CheckPoint(ret, X, Y, pl[p], mtr, Radius, Direction, Angle, IsObstracle, IsLighting)) break;
            }

            // пробегаемся по всем крайним точкам по Y
            for (int j = 0; j < mtrHeight; j++)
            {
                // стреляем в левые точки
                List<Point> pl = GetListPointInLine(X, Y, 0, j);
                for (int p = 0; p < pl.Count; p++) 
                    if (!CheckPoint(ret, X, Y, pl[p], mtr, Radius, Direction, Angle, IsObstracle, IsLighting)) break;

                // стреляем в правые точки
                pl = GetListPointInLine(X, Y, mtrWidth - 1, j);
                for (int p = 0; p < pl.Count; p++) 
                    if (!CheckPoint(ret, X, Y, pl[p], mtr, Radius, Direction, Angle, IsObstracle, IsLighting)) break;

            }
            #endregion *** построение линий и добавление освещенных точек ***

            return ret;
        }

        // проверка точки.
        // возвращает, нужно ли продолжать стрелять
        static bool CheckPoint(List<Point> ret, int plX, int plY, Point p, bool[,] mtr, int Radius, int Direction, int Angle, IsObstracleDelegate IsObstracle, IsLightingDelegate IsLighting)
        {
            // если точка не в радиусе или не в луче света И эта точка не освещена другим источником, выходим
            if(!CellInRay(plX, plY, p.X, p.Y, Radius, Direction, Angle))return false;
            if (!CellInRadius(plX, plY, p.X, p.Y, Radius) )
                if (!IsLighting(p.X, p.Y) ) return false;

            // если точка еще не проверена
            if (!mtr[p.X, p.Y])
            {
                ret.Add(p);  // добавляем точку
                mtr[p.X, p.Y] = true; // говорим, что проверена
            }

            if (IsObstracle(p.X, p.Y)) return false; // если точка является препятствием, прерываем стрельбу по этой линии

            return true;
        }

        static bool FillMtrLight(int i, int j, int[,] mtrL, int mtrW, int mtrH, int nextN, IsLightingDelegate IsLighting)
        {
            // если не выходит за границу и если еще не определено и если освещено, определяем
            if (i >= 0 && i < mtrW && j >= 0 && j < mtrH)
                if (mtrL[i, j] == 0 && IsLighting(i, j)) 
                { 
                    mtrL[i, j] = nextN; 
                    return true; 
                }
            return false;
        }

        // алгоритм нахождения всех точек линии по собственному алгоритму
        static List<Point> GetListPointInLine3(int plX, int plY, int x, int y)
        {
            List<Point> ret = new List<Point>();

            // если начальная и конечная точки совпадают, возвращаем только обе заданые точки, которые равны
            //if (plX == x & plY == y) { ret.Add(new Point(x, y)); return ret; }

            #region *** горизонталь/вертикаль ***
            // если линия горизонтальна
            if (plY == y)
            {
                if (plX < x)
                    for (int i = plX+1; i <= x; i++) ret.Add(new Point(i, y));
                else
                    for (int i = plX - 1; i >= x; i--) ret.Add(new Point(i, y));
                return ret;
            }
            // если линия вертикальна
            if (plX == x)
            {
                if (plY < y)
                    for (int j = plY + 1; j <= y; j++) ret.Add(new Point(x, j));
                else
                    for (int j = plY - 1; j >= y; j--) ret.Add(new Point(x, j));
                return ret;
            }
            #endregion *** горизонталь/вертикаль ***

            // диагональные линии
            int w = Math.Abs(plX - x), h = Math.Abs(plY - y);

            #region ***  основная и дополнительная диагонали ***
            if (w == h)
            { 
                // основная диагональ
                if (x == plX - w && y == plY - h)
                {
                    for (int i = 1; i <= w; i++)
                        ret.Add(new Point(plX - i, plY - i));
                }
                if (x == plX + w && y == plY + h)
                {
                    for (int i = 1; i <= w; i++)
                        ret.Add(new Point(plX + i, plY + i));
                }
                // дополнительная диагональ
                if (x == plX + w && y == plY - h)
                {
                    for (int i = 1; i <= w; i++)
                        ret.Add(new Point(plX + i, plY - i));
                }
                if (x == plX - w && y == plY + h)
                {
                    for (int i = 1; i <= w; i++)
                        ret.Add(new Point(plX - i, plY + i));
                }
            }
            #endregion ***  основная и дополнительная диагонали ***


            #region ***  прочие диагонали ***

            if (w < h)
            {
                if (x < plX && y < plY)
                { 
                    for(int i=1;i<=h;i++)
                        ret.Add(new Point(plX - (int)(i * (w / (double)h)), plY - i));
                }
                if (x > plX && y > plY)
                {
                    for (int i = 1; i <= h; i++)
                        ret.Add(new Point(plX + (int)(i * (w / (double)h)), plY + i));
                }
                if (x > plX && y < plY)
                {
                    for (int i = 1; i <= h; i++)
                        ret.Add(new Point(plX + (int)(i * (w / (double)h)), plY - i));
                }
                if (x < plX && y > plY)
                {
                    for (int i = 1; i <= h; i++)
                        ret.Add(new Point(plX - (int)(i * (w / (double)h)), plY + i));
                }
            }
            if (w > h)
            {
                if (x < plX && y < plY)
                {
                    for (int i = 1; i <= w; i++)
                        ret.Add(new Point(plX - i, plY - (int)(i * (h / (double)w))));
                }
                if (x > plX && y > plY)
                {
                    for (int i = 1; i <= w; i++)
                        ret.Add(new Point(plX + i, plY + (int)(i * (h / (double)w))));
                }
                if (x > plX && y < plY)
                {
                    for (int i = 1; i <= w; i++)
                        ret.Add(new Point(plX + i, plY - (int)(i * (h / (double)w))));
                }
                if (x < plX && y > plY)
                {
                    for (int i = 1; i <= w; i++)
                        ret.Add(new Point(plX - i, plY + (int)(i * (h / (double)w))));
                }
            }

            #endregion ***  прочие диагонали ***

            return ret;
        }

        // алгоритм нахождения всех точек линии по алгоритму Брезенхэма
        static List<Point> GetListPointInLine(int xstart, int ystart, int xend, int yend)
        {
            List<Point> ret = new List<Point>();

            int x, y, dx, dy, incx, incy, pdx, pdy, es, el, err;

            dx = xend - xstart;//проекция на ось икс
            dy = yend - ystart;//проекция на ось игрек

            incx = (dx > 0) ? 1 : (dx < 0) ? -1 : 0;
            /*
             * Определяем, в какую сторону нужно будет сдвигаться. Если dx < 0, т.е. отрезок идёт
             * справа налево по иксу, то incx будет равен -1.
             * Это будет использоваться в цикле постороения.
             */
            incy = (dy > 0) ? 1 : (dy < 0) ? -1 : 0;
            /*
             * Аналогично. Если рисуем отрезок снизу вверх -
             * это будет отрицательный сдвиг для y (иначе - положительный).
             */

            if (dx < 0) dx = -dx;//далее мы будем сравнивать: "if (dx < dy)"
            if (dy < 0) dy = -dy;//поэтому необходимо сделать dx = |dx|; dy = |dy|
            //эти две строчки можно записать и так: dx = Math.abs(dx); dy = Math.abs(dy);

            if (dx > dy)
            //определяем наклон отрезка:
            {
                /*
                 * Если dx > dy, то значит отрезок "вытянут" вдоль оси икс, т.е. он скорее длинный, чем высокий.
                 * Значит в цикле нужно будет идти по икс (строчка el = dx;), значит "протягивать" прямую по иксу
                 * надо в соответствии с тем, слева направо и справа налево она идёт (pdx = incx;), при этом
                 * по y сдвиг такой отсутствует.
                 */
                pdx = incx; pdy = 0;
                es = dy; el = dx;
            }
            else//случай, когда прямая скорее "высокая", чем длинная, т.е. вытянута по оси y
            {
                pdx = 0; pdy = incy;
                es = dx; el = dy;//тогда в цикле будем двигаться по y
            }

            x = xstart;
            y = ystart;
            err = el / 2;
            //ret.Add(new Point(x, y));//ставим первую точку
            //все последующие точки возможно надо сдвигать, поэтому первую ставим вне цикла

            for (int t = 0; t < el; t++)//идём по всем точкам, начиная со второй и до последней
            {
                err -= es;
                if (err < 0)
                {
                    err += el;
                    x += incx;//сдвинуть прямую (сместить вверх или вниз, если цикл проходит по иксам)
                    y += incy;//или сместить влево-вправо, если цикл проходит по y
                }
                else
                {
                    x += pdx;//продолжить тянуть прямую дальше, т.е. сдвинуть влево или вправо, если
                    y += pdy;//цикл идёт по иксу; сдвинуть вверх или вниз, если по y
                }

                ret.Add(new Point(x, y));
            }

            return ret;
        }

        // ячейка в радиусе света
        static bool CellInRadius(int plX, int plY, int x, int y, int r)
        {
            int dx = Math.Abs(plX - x);
            int dy = Math.Abs(plY - y);
            double Hyp = Math.Sqrt((dx * dx) + (dy * dy));
            return Hyp <= r;
        }

        // ячейка в луче света
        static bool CellInRay(int plX, int plY, int x, int y, int r, int direction, int angle)
        {
            // вычисляем угол до точки
            if (plX == x && plY == y) return true;

            // угол
            double ang = EMath.GetAngle(plX, plY, x, y);

            // разность между находимым углом и направлением в пределах 180 град
            double div = ang - direction;
            if (div > 180) div -= 360;
            if (div < -180) div += 360;
            div = Math.Abs(div);

            return div * 2 <= angle;

        }

        #endregion *** Освещенная область ***************************************

        #region *** Поиск пути *******************************************************

        class ETrack
        {
            public int crs;
            public int KolVoCl;
        }

        struct EWave
        {
            public int n;
            public int Val; // стоимость
            public bool Track;
        }

        #region *** внутрениие переменные *****************************
        static Point sz; // размер поля
        // параллельные массивы
        static int[,] fldW; // матрица волн
        static bool[,] fldObs; // матрица препятствий
        static int DestNum; // номер волны, поставленый на точку конечного пункта
        #endregion *** внутрениие переменные *****************************

        /// <summary>
        /// Поиск пути
        /// </summary>
        /// <param name="fldObs">Матрица препятствий (можно сгенерить функцией GenFldObs)</param>
        /// <param name="x">положение точки старта по X</param>
        /// <param name="y">положение точки старта по Y</param>
        /// <param name="xDest">положение точки назначения по X</param>
        /// <param name="yDest">положение точки назначения по Y</param>
        public static List<TrackAction> SearchWave(bool[,] FldObs, int x, int y, int xDest, int yDest)
        {
            List<TrackAction> ret = new List<TrackAction>();
            fldObs = FldObs;

            // если координаты равны, возвращаем пустой лист
            if (x == xDest && y == yDest) return ret;
            // если точка назначения - препятствие, возвращаем пустой лист
            if (fldObs[xDest, yDest]) return ret;

            sz.X = fldObs.GetUpperBound(0) + 1;
            sz.Y = fldObs.GetUpperBound(1) + 1;

            fldW = new int[sz.X, sz.Y];

            // положение персонажа в матрице волн ставим 1 в этой точке и статус "проверено"
            fldW[x, y] = 1;

            // заполняем матрицу волн
            FillFldW(xDest, yDest);

            // если точка прибытия так и не найдена, возвращаем пустой лист
            if (DestNum == 0) return ret;

            // находим путь
            ret = FillTrack(DestNum, xDest, yDest);

            return ret;

        }

        /// <summary>
        /// Поиск пути c возможностью ходить по диагонали
        /// </summary>
        /// <param name="fldObs">Матрица препятствий (можно сгенерить функцией GenFldObs)</param>
        /// <param name="x">положение точки старта по X</param>
        /// <param name="y">положение точки старта по Y</param>
        /// <param name="xDest">положение точки назначения по X</param>
        /// <param name="yDest">положение точки назначения по Y</param>
        public static List<TrackAction8> SearchWave8(bool[,] FldObs, int x, int y, int xDest, int yDest)
        {
            List<TrackAction8> ret = new List<TrackAction8>();
            fldObs = FldObs;

            // если координаты равны, возвращаем пустой лист
            if (x == xDest && y == yDest) return ret;
            // если точка назначения - препятствие, возвращаем пустой лист
            if (fldObs[xDest, yDest]) return ret;

            sz.X = fldObs.GetUpperBound(0) + 1;
            sz.Y = fldObs.GetUpperBound(1) + 1;

            fldW = new int[sz.X, sz.Y];

            // положение персонажа в матрице волн ставим 1 в этой точке и статус "проверено"
            fldW[x, y] = 1;

            // заполняем матрицу волн
            FillFldW8(xDest, yDest);

            // если точка прибытия так и не найдена, возвращаем пустой лист
            if (DestNum == 0) return ret;

            // находим путь
            ret = FillTrack8(DestNum, xDest, yDest);

            return ret;
        }

        #region *** внутрениие функции *****************************

        #region *** 4 ***********************************************************

        // заполнение матрицы волн
        static void FillFldW(int xDest, int yDest)
        {
            // заполняем матрицу волн
            int ActNum = 2; // текущий номер волны, которым заполняем матрицу
            bool bFill = true; // как минимум 1 клетка была заполнена
            DestNum = 0; // номер волны, поставленый на точку конечного пункта

            while (bFill)
            {
                bFill = false;
                // пробегаемся по матрице
                for (int i = 0; i < sz.X; i++)
                {
                    for (int j = 0; j < sz.Y; j++)
                    {
                        // если найдено нужное число (текущий номер волны - 1), заполняем соседние с ним клетки текущим номером волны
                        if (fldW[i, j] == (ActNum - 1))
                        {
                            if (FillNearCells(ActNum, i, j, xDest, yDest)) bFill = true;
                            // если точка прибытия найдена, выходим
                            if (DestNum != 0) return;
                        }
                    }
                }
                ActNum++;
            }
        }

        // заполнение матрицы волн вокруг точки
        // если находится точка прибытия, ставим ее номер, говорящий, что точка достигнута и дальше заполнять не нужно
        static bool FillNearCells(int num, int x, int y, int xDest, int yDest)
        {
            bool ret = false;
            // вверх       
            if (y > 0) // если это не граница
                if (fldW[x, y - 1] == 0) // если еще не заполнена
                    if (!fldObs[x, y - 1]) // если не препятствие, заполняем
                    {
                        fldW[x, y - 1] = num;
                        // если это точка прибытия, ставим ее номер
                        if (x == xDest && (y - 1) == yDest) DestNum = num;
                        ret = true;
                    }
            // вниз       
            if (y < (sz.Y - 1)) // если это не граница
                if (fldW[x, y + 1] == 0) // если еще не заполнена
                    if (!fldObs[x, y + 1]) // если не препятствие, заполняем
                    {
                        fldW[x, y + 1] = num;
                        // если это точка прибытия, ставим ее номер
                        if (x == xDest && (y + 1) == yDest) DestNum = num;
                        ret = true;
                    }
            // влево       
            if (x > 0) // если это не граница
                if (fldW[x - 1, y] == 0) // если еще не заполнена
                    if (!fldObs[x - 1, y]) // если не препятствие, заполняем
                    {
                        fldW[x - 1, y] = num;
                        // если это точка прибытия, ставим ее номер
                        if ((x - 1) == xDest && y == yDest) DestNum = num;
                        ret = true;
                    }
            // вправо       
            if (x < (sz.X - 1)) // если это не граница
                if (fldW[x + 1, y] == 0) // если еще не заполнена
                    if (!fldObs[x + 1, y]) // если не препятствие, заполняем
                    {
                        fldW[x + 1, y] = num;
                        // если это точка прибытия, ставим ее номер
                        if ((x + 1) == xDest && y == yDest) DestNum = num;
                        ret = true;
                    }

            return ret;
        }

        // поиск пути по матрице волн
        static List<TrackAction> FillTrack(int DestNum, int xDest, int yDest)
        {
            List<TrackAction> trk = new List<TrackAction>();
            int x = xDest;
            int y = yDest;
            // пробегаемся от номера волны пункта назначения, до пункта отправки
            // n - номер ячейки, куда идти
            for (int n = (DestNum - 1); n >= 1; n--)
            {
                // выбираем соседнюю ячейку текущим номером
                // смотрим вверх
                if (y > 0) // если это не граница
                    if (fldW[x, y - 1] == n)// если номер найден, выставляем новый курс
                    {
                        y--;
                        n = fldW[x, y];
                        // добавляем следующий шаг
                        trk.Insert(0, TrackAction.moveDown);
                        continue;
                    }

                // смотрим вниз
                if (y < (sz.Y - 1)) // если это не граница
                    if (fldW[x, y + 1] == n)// если номер найден, выставляем новый курс
                    {
                        y++;
                        n = fldW[x, y];
                        // добавляем следующий шаг
                        trk.Insert(0, TrackAction.moveUp);
                        continue;
                    }

                // смотрим влево
                if (x > 0) // если это не граница
                    if (fldW[x - 1, y] == n)// если номер найден, выставляем новый курс
                    {
                        x--;
                        n = fldW[x, y];
                        // добавляем следующий шаг
                        trk.Insert(0, TrackAction.moveRight);
                        continue;
                    }

                // смотрим вправо
                if (x < (sz.X - 1)) // если это не граница
                    if (fldW[x + 1, y] == n)// если номер найден, выставляем новый курс
                    {
                        x++;
                        n = fldW[x, y];
                        // добавляем следующий шаг
                        trk.Insert(0, TrackAction.moveLeft);
                        continue;
                    }

            }
            return trk;
        }

        #endregion *** 4 ***********************************************************
        // ***********************************************************************
        #region *** 8 ***********************************************************

        // заполнение матрицы волн
        static void FillFldW8(int xDest, int yDest)
        {
            // заполняем матрицу волн
            int ActNum = 2; // текущий номер волны, которым заполняем матрицу
            bool bFill = true; // как минимум 1 клетка была заполнена
            DestNum = 0; // номер волны, поставленый на точку конечного пункта

            while (bFill)
            {
                bFill = false;
                // пробегаемся по матрице
                for (int i = 0; i < sz.X; i++)
                {
                    for (int j = 0; j < sz.Y; j++)
                    {
                        // если найдено нужное число (текущий номер волны - 1), заполняем соседние с ним клетки текущим номером волны
                        if (fldW[i, j] == (ActNum - 1))
                        {
                            if (FillNearCells8(ActNum, i, j, xDest, yDest)) bFill = true;
                            // если точка прибытия найдена, выходим
                            if (DestNum != 0) return;
                        }
                    }
                }
                ActNum++;
            }
        }

        // заполнение матрицы волн вокруг точки
        // если находится точка прибытия, ставим ее номер, говорящий, что точка достигнута и дальше заполнять не нужно
        static bool FillNearCells8(int num, int x, int y, int xDest, int yDest)
        {
            bool ret = false;
            // вверх (влево, вправо)      
            if (y > 0) // если это не граница
            {
                // вверх
                if (fldW[x, y - 1] == 0) // если еще не заполнена
                    if (!fldObs[x, y - 1]) // если не препятствие, заполняем
                    {
                        fldW[x, y - 1] = num;
                        // если это точка прибытия, ставим ее номер
                        if (x == xDest && (y - 1) == yDest) DestNum = num;
                        ret = true;
                    }
                // вверх-влево
                if (x > 0) // если это не граница
                {
                    if (fldW[x - 1, y - 1] == 0) // если еще не заполнена
                        if (!fldObs[x - 1, y - 1]) // если не препятствие, заполняем
                        {
                            fldW[x - 1, y - 1] = num;
                            // если это точка прибытия, ставим ее номер
                            if ((x - 1) == xDest && (y - 1) == yDest) DestNum = num;
                            ret = true;
                        }
                }
                // вверх-вправо
                if (x < (sz.X - 1)) // если это не граница
                {
                    if (fldW[x + 1, y - 1] == 0) // если еще не заполнена
                        if (!fldObs[x + 1, y - 1]) // если не препятствие, заполняем
                        {
                            fldW[x + 1, y - 1] = num;
                            // если это точка прибытия, ставим ее номер
                            if ((x + 1) == xDest && (y - 1) == yDest) DestNum = num;
                            ret = true;
                        }
                }
            }
            // вниз (влево вправо)      
            if (y < (sz.Y - 1)) // если это не граница
            {
                if (fldW[x, y + 1] == 0) // если еще не заполнена
                    if (!fldObs[x, y + 1]) // если не препятствие, заполняем
                    {
                        fldW[x, y + 1] = num;
                        // если это точка прибытия, ставим ее номер
                        if (x == xDest && (y + 1) == yDest) DestNum = num;
                        ret = true;
                    }
                // вниз-влево
                if (x > 0) // если это не граница
                {
                    if (fldW[x - 1, y + 1] == 0) // если еще не заполнена
                        if (!fldObs[x - 1, y + 1]) // если не препятствие, заполняем
                        {
                            fldW[x - 1, y + 1] = num;
                            // если это точка прибытия, ставим ее номер
                            if ((x - 1) == xDest && (y + 1) == yDest) DestNum = num;
                            ret = true;
                        }
                }
                // вниз-вправо
                if (x < (sz.X - 1)) // если это не граница
                {
                    if (fldW[x + 1, y + 1] == 0) // если еще не заполнена
                        if (!fldObs[x + 1, y + 1]) // если не препятствие, заполняем
                        {
                            fldW[x + 1, y + 1] = num;
                            // если это точка прибытия, ставим ее номер
                            if ((x + 1) == xDest && (y + 1) == yDest) DestNum = num;
                            ret = true;
                        }
                }
            }
            // влево       
            if (x > 0) // если это не граница
                if (fldW[x - 1, y] == 0) // если еще не заполнена
                    if (!fldObs[x - 1, y]) // если не препятствие, заполняем
                    {
                        fldW[x - 1, y] = num;
                        // если это точка прибытия, ставим ее номер
                        if ((x - 1) == xDest && y == yDest) DestNum = num;
                        ret = true;
                    }
            // вправо       
            if (x < (sz.X - 1)) // если это не граница
                if (fldW[x + 1, y] == 0) // если еще не заполнена
                    if (!fldObs[x + 1, y]) // если не препятствие, заполняем
                    {
                        fldW[x + 1, y] = num;
                        // если это точка прибытия, ставим ее номер
                        if ((x + 1) == xDest && y == yDest) DestNum = num;
                        ret = true;
                    }

            return ret;
        }

        // поиск пути по матрице волн
        static List<TrackAction8> FillTrack8(int DestNum, int xDest, int yDest)
        {
            List<TrackAction8> trk = new List<TrackAction8>();
            int x = xDest;
            int y = yDest;
            // пробегаемся от номера волны пункта назначения, до пункта отправки
            // n - номер ячейки, куда идти
            for (int n = (DestNum - 1); n >= 1; n--)
            {
                // выбираем соседнюю ячейку текущим номером

                // смотрим вверх
                if (y > 0) // если это не граница
                    if (fldW[x, y - 1] == n)// если номер найден, выставляем новый курс
                    {
                        y--;
                        n = fldW[x, y];
                        // добавляем следующий шаг
                        trk.Insert(0, TrackAction8.moveDown);
                        continue;
                    }

                // смотрим вниз
                if (y < (sz.Y - 1)) // если это не граница
                    if (fldW[x, y + 1] == n)// если номер найден, выставляем новый курс
                    {
                        y++;
                        n = fldW[x, y];
                        // добавляем следующий шаг
                        trk.Insert(0, TrackAction8.moveUp);
                        continue;
                    }

                // смотрим влево
                if (x > 0) // если это не граница
                    if (fldW[x - 1, y] == n)// если номер найден, выставляем новый курс
                    {
                        x--;
                        n = fldW[x, y];
                        // добавляем следующий шаг
                        trk.Insert(0, TrackAction8.moveRight);
                        continue;
                    }

                // смотрим вправо
                if (x < (sz.X - 1)) // если это не граница
                    if (fldW[x + 1, y] == n)// если номер найден, выставляем новый курс
                    {
                        x++;
                        n = fldW[x, y];
                        // добавляем следующий шаг
                        trk.Insert(0, TrackAction8.moveLeft);
                        continue;
                    }

                // смотрим вверх-влево
                if (x > 0 && y > 0) // если это не граница
                    if (fldW[x - 1, y - 1] == n)// если номер найден, выставляем новый курс
                    {
                        x--;
                        y--;
                        n = fldW[x, y];
                        // добавляем следующий шаг
                        trk.Insert(0, TrackAction8.moveDownRight);
                        continue;
                    }

                // смотрим вверх-вправо
                if (x < (sz.X - 1) && y > 0) // если это не граница
                    if (fldW[x + 1, y - 1] == n)// если номер найден, выставляем новый курс
                    {
                        x++;
                        y--;
                        n = fldW[x, y];
                        // добавляем следующий шаг
                        trk.Insert(0, TrackAction8.moveDownLeft);
                        continue;
                    }

                // смотрим вниз-влево
                if (x > 0 && y < (sz.Y - 1)) // если это не граница
                    if (fldW[x - 1, y + 1] == n)// если номер найден, выставляем новый курс
                    {
                        x--;
                        y++;
                        n = fldW[x, y];
                        // добавляем следующий шаг
                        trk.Insert(0, TrackAction8.moveUpRight);
                        continue;
                    }

                // смотрим вниз-вправо
                if (x < (sz.X - 1) && y < (sz.Y - 1)) // если это не граница
                    if (fldW[x + 1, y + 1] == n)// если номер найден, выставляем новый курс
                    {
                        x++;
                        y++;
                        n = fldW[x, y];
                        // добавляем следующий шаг
                        trk.Insert(0, TrackAction8.moveUpLeft);
                        continue;
                    }

            }
            return trk;
        }

        #endregion *** 8 ***********************************************************

        #endregion *** внутрениие функции *****************************

        #region *** генерация булевой матрицы препятствий **************************

        /// <summary>
        /// Сгенерить матрицу препятствий для поиска пути
        /// </summary>
        /// <param name="fldSzX">ширина пользуемой матрицы</param>
        /// <param name="fldSzY">высота пользуемой матрицы</param>
        /// <param name="IsObs">функция, определяющая препятствие</param>
        public static bool[,] GenFldObs(int fldSzX, int fldSzY, IsObstracleDelegate IsObs)
        {
            bool[,] b = new bool[fldSzX, fldSzY];
            for (int i = 0; i < fldSzX; i++)
                for (int j = 0; j < fldSzY; j++)
                    b[i, j] = IsObs(i, j);
            return b;
        }

        /// <summary>
        /// Сгенерить матрицу препятствий для поиска пути
        /// </summary>
        /// <param name="fldSzX">ширина пользуемой матрицы</param>
        /// <param name="fldSzY">высота пользуемой матрицы</param>
        /// <param name="IsObs">функция, определяющая препятствие</param>
        /// <param name="rect">ограницивающий прямоугольнык, в котором искать путь</param>
        public static bool[,] GenFldObs(int fldSzX, int fldSzY, IsObstracleDelegate IsObs, Rectangle rect)
        {
            bool[,] b = new bool[rect.Width, rect.Height];
            for (int i = 0; i < rect.X; i++)
                for (int j = 0; j < rect.Y; j++)
                {
                    int x = rect.X + i;
                    int y = rect.Y + j;
                    if (x >= 0 & x < fldSzX & y >= 0 & y < fldSzY)
                        b[i, j] = IsObs(x, y);
                }
            return b;
        }

        #endregion *** генерация булевой матрицы препятствий **************************

        #endregion *** Поиск пути *******************************************************

    }

}
